#ifndef DoubleLinkedList_H
#define DoubleLinkedList_H

#include <iostream>
using namespace std;

template<typename DT>
struct Node
{
  DT value;
  Node* pre;
  Node* nxt;
public:
  Node(){}
  Node(DT t, Node *pre, Node *nxt)
  {
    this->value = t;
    this->pre = pre;
    this->nxt = nxt;
  }
};

template<typename DT>
class DoubleLinkList
{
 private:
  Node<DT>* head;
  Node<DT>* tail;
  Node<DT>* pos_Node(int idx);
  int count;
 public:
  int get_size();
  DoubleLinkList();
  ~DoubleLinkList();
  DT read_Node(int idx);
  void read_all();
  void insert_Node(int idx,DT val);
  void delete_Node(int idx);
  int iterator_find(DoubleLinkList<DT>* _list,DT _val);
  void _error(int er);
};

template<typename DT>
int DoubleLinkList<DT>::get_size()
{
  return count;
}

template<typename DT>
Node<DT>* DoubleLinkList<DT>::pos_Node(int idx)
{
  if(idx > count || idx < 0)
    {
      cout << "Position doesn't exist." << endl;
      return nullptr;
    }
  else
    {
      int k = 0;
      Node<DT>* pos = head->nxt;
      while(k++ < idx)
	pos = pos->nxt;
      return pos;
    }
};

template<typename DT>
DoubleLinkList<DT>::DoubleLinkList()
{
  head = new Node<DT>();
  tail = new Node<DT>();
  
  head->pre = head;
  head->nxt = tail;
  count = 0;
};

template<typename DT>
DoubleLinkList<DT>::~DoubleLinkList()
{
  Node<DT>* ee;
  Node<DT>* kill = head->nxt;
  while(kill != head && kill != tail);
  {
	ee = kill;
	kill = kill->nxt;
	delete ee;

  }
  delete head;
  delete tail;
  head = nullptr;
  tail = nullptr;
};

template<typename DT>
DT DoubleLinkList<DT>::read_Node(int idx)
{
  return pos_Node(idx)->value;
};

template<typename DT>
void DoubleLinkList<DT>::insert_Node(int idx,DT t)
{
  if(idx != 0 && idx != count)
    {
      Node<DT>* pos_idx  =  pos_Node(idx);
      Node<DT>* node = new Node<DT>(t, pos_idx->pre, pos_idx);
      pos_idx->pre->nxt = node;
      pos_idx->pre = node;
      node->value = t;
      count++;
    }
  else if(idx == 0)
    {
      Node<DT>* pos_idx = pos_Node(idx);
      Node<DT>* node = new Node<DT>(t, head , head->nxt);
      head->nxt->pre = node;
      head->nxt = node;
      node->value = t;
      count++;
    }
  else if(idx == count)
    {
      Node<DT>* pos_idx = pos_Node(idx);
      Node<DT>* node = new Node<DT>(t,tail->pre,tail);
      tail->pre->nxt = node;
      tail->pre = node;
      node->value = t;
      count++;
    } 
};

template<typename DT>
void DoubleLinkList<DT>::delete_Node(int idx)
{
  Node<DT>* pos_idx = pos_Node(idx);
  pos_idx->pre->nxt = pos_idx->nxt;
  pos_idx->nxt->pre = pos_idx->pre;
  delete pos_idx;
  count--;
  cout << endl << "Node " << idx <<  " has been deleted." << endl;
};

template<typename DT>
void DoubleLinkList<DT>::read_all()
{
  int arknights;
  for(arknights = 0;arknights < count; arknights++)
    cout << read_Node(arknights) << " ";
};

template<typename DT>
int DoubleLinkList<DT>::iterator_find(DoubleLinkList<DT>* _list, DT _val)
{
  int j = 0;
  Node<DT>* finder = _list->head->nxt;
  while(finder != tail)
    {
      if(finder->value == _val)
	return j;
      else
	{
	  finder = finder->nxt;
	  j++;
	}
    }
  if(finder == tail)
    return -1;
  else
    return -1;
};

template<typename DT>
void DoubleLinkList<DT>::_error(int er)
{
  if(er < 0)
    cout <<  endl << "Doesn't exist" << endl;
}


#else

#endif
  
